package me.mingshan.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.cn/problems/combination-sum-iv/description/
 *
 * 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
 *
 * 题目数据保证答案符合 32 位整数范围。数组内的数字各不相同。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3], target = 4
 * 输出：7
 * 解释：
 * 所有可能的组合为：
 * (1, 1, 1, 1)
 * (1, 1, 2)
 * (1, 2, 1)
 * (1, 3)
 * (2, 1, 1)
 * (2, 2)
 * (3, 1)
 * 请注意，顺序不同的序列被视作不同的组合。
 * 示例 2：
 *
 * 输入：nums = [9], target = 3
 * 输出：0
 *
 *
 * @author hanjuntao
 * @date 2025/7/23 0023
 */
public class L_377_combination_sum_iv {
    private static final Map<Integer,  Integer> CACHE = new HashMap<>();

    public static void main(String[] args) {
        int[] source = {1, 2, 3};
        int target = 4;
        System.out.println(combinationSum4_3(source, target));
        // 7

        source = new int[]{9};
        target = 3;
        System.out.println(combinationSum4_3(source, target));
        // 0

        source = new int[]{3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25};
        target = 10;
        System.out.println(combinationSum4_3(source, target));
        // 9
    }

    /**
     * 从题目描述中，可以得到：
     *
     * 1. 数组内元素各不相同
     * 2. 可以使用数组内元素任意次
     * 3. 顺序不同算不同
     *
     * 关键点：
     *  1. 数字可以重复使用。
     *  2. 顺序不同视为不同的组合（实际上是排列）。
     *
     *
     * 该题可以转化为爬楼梯问题：
     *
     * 楼梯数为 target，
     * 每次爬楼梯，可以选择从数组中任意选择一个数字，代表可以爬几个台阶
     *
     *
     * https://leetcode.cn/problems/combination-sum-iv/solutions/2268310/zhe-dao-ti-bu-jiu-shi-pa-lou-ti-yao-by-j-h5nn
     *
     * @param nums
     * @param target
     * @return
     */
    public static int combinationSum4(int[] nums, int target) {
        // 定义dp[i] 表示爬到i阶台阶的方法数
        int[] dp = new int[target + 1];

        // 0阶台阶，只有一种方法
        dp[0] = 1;

        for (int i = 1; i <= target; i++) {
            // 以前只能走一步或者两步的时候，把两个步的组合数相加，得到当前i的组合数
            //  dp[i] = dp[i - 1] + dp[i - 2];
            // 现在当前要想上到这个i台阶，可以从数组中任选一个数，
            // 但是必须要满足 i >= nums[j]，因为跨的步长不能超过楼梯的台阶数i

            for (int j = 0; j < nums.length; j++) {
                if (i >= nums[j]) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }

        return dp[target];
    }

    /**
     * 递归解法
     *
     * @param nums
     * @param target
     * @return
     */
    public static int combinationSum4_1(int[] nums, int target) {
        if (target == 0) {
            return 1;
        }

        int result = 0;

        for (int i = 0; i < nums.length; i++) {
            if (target >= nums[i]) {
                result  += combinationSum4_1(nums, target - nums[i]);
            }
        }

        return result;
    }

    public static int combinationSum4_3(int[] nums, int target) {
        int[] memo = new int[target + 1];
        Arrays.fill(memo, -1);
        return dfs(target, nums, memo);
    }

    private static int dfs(int i, int[] nums, int[] memo) {
        if (i == 0) { // 爬完了
            return 1;
        }
        if (memo[i] != -1) { // 之前计算过
            return memo[i];
        }
        int res = 0;
        for (int x : nums) { // 枚举所有可以爬的台阶数
            if (x <= i) {
                res += dfs(i - x, nums, memo);
            }
        }
        return memo[i] = res; // 记忆化
    }

}
